//
// Created by Administrator on 2021/9/9.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    int findJudge(int n, vector<vector<int>> &trust) {
        // 法官：所有人都相信————找到所有人信任的人的交集
        // 不相信任何人：不能出现在trust列表的第一位
        // 构造二维矩阵 信任关系图
        vector<vector<bool>> trustMap(n + 1, vector<bool>(n + 1, false));
        for (int i = 1; i <= n; ++i) {
            trustMap[i][i] = true;
        }
        unordered_set<int> seen;
        for (auto &x: trust) {
            trustMap[x[0]][x[1]] = true;
            seen.insert(x[0]);
        }
        for (int i = 1; i <= n; ++i) {
            if (seen.count(i))
                continue;
            int j = 1;
            for (; j <= n; ++j) {
                if (!trustMap[j][i])
                    break;
            }
            if (j == n + 1)
                return i;
        }
        return -1;
    }

    int findJudge2(int n, vector<vector<int>> &trust) {
        // 出度为0 入度为n-1
        vector<vector<int>> degree(n + 1, vector<int>(2, 0));
        for (auto &x: trust) {
            degree[x[0]][1]++; // 出度
            degree[x[1]][0]++; // 入度
        }
        for (int i = 1; i <= n; ++i) {
            if (degree[i][0] == n - 1 and degree[i][1] == 0)
                return i;
        }
        return -1;
    }

    int findJudge3(int n, vector<vector<int>> &trust) {
        // 用 入度 - 出度 作为判断依据
        vector<int>degree(n + 1, 0);
        for (auto &x: trust) {
            --degree[x[0]]; // 出度
            ++degree[x[1]]; // 入度
        }
        for (int i = 1; i <= n; ++i) {
            if (degree[i] == n - 1)
                return i;
        }
        return -1;
    }

};

int main() {
    vector<vector<int>> trust{{1, 3},
                              {2, 3}};
    Solution solution;
    cout << solution.findJudge3(3, trust) << endl;
    return 0;
}
